package com.sicheng.lc.杂题.二叉树;

import leetcode.editor.cn.tree.TreeNode;

import java.util.ArrayDeque;
import java.util.HashMap;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/7 23:33
 */
public class 二叉树每层的叶子 {
    // 层序遍历比较优雅的板子(bfs基本原理拓展而来), 用一个变量存储本层结点个数
    // 以本层结点扩展下一层结点,记录下一层节点总个数
    public int countLeaves(TreeNode root) {
        if (root == null)
            return 0;
        ArrayDeque<TreeNode> deque = new ArrayDeque<>();
        // 本层结点个数,初始是1第一层只有一个root结点
        int res = 0;
        deque.offer(root);
        while (!deque.isEmpty()) {
            // 以本层结点扩展下一层结点
            int size = deque.size();
            for (int i = 0; i < size; i++) {

                if (deque.isEmpty())
                    break;

                TreeNode node = deque.poll();
                if (node.left == null && node.right == null) {
                    res++;
                    continue;
                }
                if (node.left != null) {
                    deque.offer(node.left);
                }
                if (node.right != null) {
                    deque.offer(node.right);
                }
            }
        }


        return res;
    }

    // 费空间 不好 留着以后回首看自己的傻逼时刻
    private int hash(TreeNode root) {
        int[] counts = new int[(int) 1e5];
        ArrayDeque<TreeNode> deque = new ArrayDeque<>();
        HashMap<TreeNode, Integer> layer = new HashMap<>();
        deque.offer(root);
        layer.put(root, 0);
        int n = 0;
        while (!deque.isEmpty()) {
            TreeNode node = deque.poll();
            int x = layer.get(node);
            if (node.left == null && node.right == null) {
                counts[x]++;
                continue;
            }
            if (node.left != null) {
                n = Math.max(n, x + 1);
                layer.put(node.left, x + 1);
                deque.offer(node.left);
            }
            if (node.right != null) {
                n = Math.max(n, x + 1);
                layer.put(node.right, x + 1);
                deque.offer(node.right);
            }
        }
        int res = 0;

        for (int i = 0; i <= n; i++) {
            res += counts[i];
        }

        return res;
    }
}
